from typing import List


def func(nums: List):
    # i: 0 -> len(nums)
    # j: 0 -> i
    # if nums[i]>nums[j]:
    # dp[i] = max(dp[i], dp[j] + 1)
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(0, len(nums)):
        # dp.append(1)
        for j in range(0, i):
            # 如果要求非严格递增，将 '>' 改为 '>=' 即可。
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)


# 返回该最长子序列
def func1(nums: List):
    tails, res = [0] * len(nums), 0
    ans, max_len = [], 0
    for num in nums:
        i, j = 0, res
        while i < j:
            m = (i + j) // 2
            if tails[m] < num:
                i = m + 1  # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
            else:
                j = m
        tails[i] = num
        if j == res:
            res += 1
        if res > max_len:
            ans = tails[:res]
    return ans


if __name__ == '__main__':
    test = [9, 2, 5, 3, 7, 21, 18]
    t = [7, 8, 1, 2, 10]
    print(func1(t))

